package alg;

public class Math {

	public static long inv(long num, long mod)
	{
		long k = exteuclid(num, mod)[0];
		if (k < 0)
			k = mod + k;
		return k;
	}
	
	public static int gcd(int x, int p)
	{
		int a = x;
		int b = p;
		while(b != 0)
		{
			int t = b;
			b = a % b;
			a = t;
		}
		
		return a;
	}
	
	public static long minmod(long x, long y, long p)
	{
		if (x < 0 || y < 0)
		{
			System.out.println("ERROR!");
			throw new RuntimeException("ERROR: mod minus negative number");
		}
		
		long xx = x % p;
		long yy = y % p;
		
		if (xx < yy)
			return p + (xx-yy);
		return xx-yy;
	}
	
	public static long addmod(long x, long y, long p)
	{
		if (x < 0 || y < 0)
		{
			System.out.println("ERROR!");
			throw new RuntimeException("ERROR: mod add negative number");
		}
		
		return (x+y)%p;
	}
	
	public static long multmod(long x, long y, long p)
	{
		if (x < 0 || y < 0)
		{
			System.out.println("ERROR!");
			throw new RuntimeException("ERROR: mod mult negative number");
		}
		
		return (x*y)%p;
	}
	
	public static long divmod(long x, long y, long p)
	{
		if (x < 0 || y < 0)
		{
			System.out.println("ERROR!");
			throw new RuntimeException("ERROR: mod div negative number");
		}
		else if (y == 0)
		{
			System.out.println("ERROR!");
			throw new RuntimeException("ERROR: mod div zero");
		}
		
		return multmod(x, inv(y,p), p);
	}
	
	public static long[] exteuclid(long x, long p)
	{
		if (p == 0)
			return new long[] {1, 0};
		
		long q = x / p;
		long r = x % p;
		long[] k = exteuclid(p, r);
		return new long[] { k[1], k[0] - q*k[1] };
	}
}

/*function extended_gcd(a, b)
if b = 0
    return (1, 0)
else
    (q, r) := divide (a, b)
    (s, t) := extended_gcd(b, r)
    return (t, s - q * t)*/